#include<iostream>
#include<string.h>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;

//插入排序
void InsertSort(vector<int>& a)
{
  int n = a.size();
  for(int i = 0 ;i<n - 1;i++)
  {
    int end = i;    
    int x  = a[end+1]; //将x插入到[0,end]的有序区间
    while(end >= 0)
    {
      if(a[end] >x)
      {
        a[end+1] = a[end];
        end -=1;
      }
      else 
      {
        break;
      }
    }
    a[end+1] = x;
  }
}

//写法1:多组一起排序
void ShellSort(vector<int>& a)
{
  int gap = a.size();
  int n = a.size();
  while(gap > 1)
  {
    gap /=2 ; //gap = gap /3 + 1;
    for(int i = 0 ;i<n-gap;i++) //注意:这里循环变量每次+1
    {
       int end = i;
       int x = a[end+gap];
       while(end>=0)
       {
          if(a[end] > x)
          {
            a[end+gap] = a[end];
            end-=gap;
          }
          else 
            break;
       }
       a[end+gap] = x;
    }
  }
}
//版本2:一组一组排序, 一共分为gap组,gap为每一组之间元素的间隔
void ShellSort_versio2(vector<int>& a)
{
  int n = a.size();
  int gap =  n;
  while(gap >1)
  {
    gap /=2 ; //gap = gap /3 + 1;
    for(int j = 0;j<gap;j++) //一共排序gap组
    {
      //需要注意：每一组开头的位置都是不一样的,如果每一次都以i=0为开始,那就是对同一组进行排序了
      //每一组的开头就是j 需要注意i的初始值为j而不是0
      for(int i = j ; i <n - gap;i+=gap) //注意这里循环遍历每次+=gap
      {
         int end = i;
         int x = a[end+gap];
         while(end>=0)
         {
           if(a[end] > x)
           {
             a[end+gap]  = a[end];
             end-=gap;
           }
           else 
           {
             break;
           }
         }
         a[end+gap] = x;
      }
    }
  }
}
//选择排序 -一次选择一个数的版本
void SelectSort(vector<int>& a)
{
    int n = a.size()-1;
    for(int i = n;i>=0;i--)
    {
      //每次在[0,i]范围上选择一个最大的数
      int maxi = i;
      for(int j = 0 ;j < i;j++)
      {
        if(a[j] > a[maxi]) maxi = j;
      }
      swap(a[n--],a[maxi]);
    }
}
//一次选择两个数的版本
void SelectSort_version2(vector<int>& a)
{
  int begin = 0,end = a.size()-1;
  while(begin < end)
  {
    //在[begin,end]的范围进行选择,然后把最大值放到end位置,最小值放到begin位置,然后缩小区间
    int maxi = begin,mini = begin;
    for(int i = begin;i<=end;i++)
    {
      if(a[i] > a[maxi]) maxi = i;
      if(a[i] < a[mini]) mini = i;
    }
    swap(a[mini],a[begin]);
    if(maxi == begin)
    {
      maxi = mini;
    }
    swap(a[maxi],a[end]);
    begin++,end--;
  }
}
//最后n:表示当前堆中有多少个元素(认为0~n-1)的元素是在堆里面的
void AdjustDown(vector<int>& a,int parent,int n)
{
  int child = parent*2+1;
  while(child < n)
  {
    if(child+1<n && a[child+1]>a[child])
      child+=1;
    if(a[child] > a[parent])
    {
      swap(a[child],a[parent]);
      parent = child ;
      child = parent*2+1;
    }
    else {
      break;
    }
  }
}
//排升序,建大堆 ->每次选出最大的元素放在最后面
void HeapSort(vector<int>& a)
{
  //从最后一个叶子节点的父亲节点开始建堆
  //parent = (child-1)/2   left_child = parent*2+1 right_child = parent*2+2
  int lastParent = (a.size()-1-1)/2;
  for(int i = lastParent;i>=0;i--)
  {
    AdjustDown(a,i,a.size());
  }
  int end = a.size()-1;
  while(end > 0)
  {
    swap(a[end],a[0]);
    AdjustDown(a,0,end);
    end--;
  }
}

//交换排序
void BubbleSort(vector<int>& a)
{
  int n  = a.size();
  //每一趟排序,可以排好一个数,n个数,只需要排序n-1趟
  for(int i = 0;i<n-1;i++)
  {
    //每一趟可以少比较一个数: 所以要-i
    //最初:n个数,只需要比较n-1组
    bool flag = true;
    for(int j = 0 ;j<n-1-i;j++)
    { 
        if(a[j]> a[j+1])
          swap(a[j],a[j+1]),flag = false;
    }
    if(flag)
      break;
  }
}
//hoare版本
int PartSion1(vector<int>& a,int left,int right)
{
  int keyi = left;
  //当left和right指向同一个值的时候,跳出循环
  //如果循环条件写成:left<=right就是错误的,因为可能导致left越界
  while(left<right) 
  {
    while(left<right && a[right]>=a[keyi])
      right--;
    while(left<right && a[left]<=a[keyi])
      left++;
    ::swap(a[left],a[right]);
  }
  ::swap(a[left],a[keyi]);
  return left;
}

//挖坑法
int PartSion2(vector<int>& a,int left,int right)
{
  int key = a[left];
  int pivot = left;
  while(left < right)
  {
    while(left<right && a[right] >= key)
    {
      right--;
    }
    a[pivot] = a[right];
    pivot = right;

    while(left<right && a[left] <= key)
    {
      left++;
    }
    a[pivot] = a[left];
    pivot = left;
  }
  a[pivot] = key;
  return pivot;
}
//前后指针法
int PartSion3_version1(vector<int>& v,int left,int right)
{
  int keyi = left;
  int prev = left;
  int cur = prev+1;
  while(cur<=right)
  {
    while(cur <= right && v[cur] >= v[keyi]) //找严格比v[keyi小的]
      cur++;
    if(cur <= right )
      swap(v[cur++],v[++prev]);
  }
  swap(v[prev],v[keyi]);
  return prev;
}
int PartSion3_version2(vector<int>& v,int left,int right)
{
  int prev = left;
  int cur = prev+1;
  while(cur<=right)
  {
    while(cur <= right && v[cur]>=v[left])
    {
      cur ++;
    }
    if(cur <= right)
      swap(v[cur++],v[++prev]);
  }
  swap(v[prev],v[left]);//最后把left位置的值和prev位置的值交换
  //此时prev左边位置的值都比v[left]小,右边的值都比v[left]大
  return prev;
}
//简化版本->无论是交换完成还是找小,cur都要往后走,所以可以写成一个逻辑
//cur找小,找到小的就和++prev下标的值交换,然后cur再往后走,   cur找不到小->cur++
int PartSion3_version3(vector<int>& v,int left,int right)
{
  int prev = left;
  int cur = prev+1;
  while(cur<=right)
  {
    if(v[cur] < v[left]) //cur指向的值,严格比v[left]小的
    {
      swap(v[cur],v[++prev]);
    }
    cur ++;//不管怎么样都要向后走
  }
  swap(v[left],v[prev]);
  return prev;
}
//最精简版本 ->当找到cur和++prev指向的是同一个元素时,可以不交换
int PartSion3_version4(vector<int>& v,int left,int right)
{
  int prev = left;
  int cur = prev+1;
  while(cur<=right)
  {
    if(v[cur] < v[left] && cur != ++prev) //找到严格比v[left]小的,并且cur指向的和++prev指向的值不一样
    {
      swap(v[cur],v[prev]); //注意：这里prev不可以++ 因为上面if条件已经++过了
    }
    cur ++;
  }
  swap(v[left],v[prev]);
  return prev;
}
void QucikSort(vector<int>& a,int left,int right)
{
    if(left >= right)
      return ;
    int keyi = PartSion3_version4(a,left,right);
    //[left,keyi-1] [keyi+1,right]
    QucikSort(a,left,keyi-1);
    QucikSort(a,keyi+1,right);
}


void _MergeSort(vector<int>& a,int left,int right,vector<int>& tmp)
{
    if(left >= right)  //注意！！！如果不加这个,下面就会越界访问了
      return  ;
    int mid = (left+right)/2;
    //[left,mid][mid+1,right]
    _MergeSort(a,left,mid,tmp);
    _MergeSort(a,mid+1,right,tmp);

    int begin1 = left,end1 = mid;
    int begin2 = mid+1,end2 = right;
    int index = left;//注意起始下标是left,不是0！！！
    while(begin1<=end1 && begin2<=end2)
    {
      if(a[begin1] < a[begin2])
        tmp[index++] = a[begin1++];
      else
        tmp[index++] = a[begin2++];
    }
    while(begin1<=end1)
      tmp[index++] = a[begin1++];
    while(begin2<=end2)
      tmp[index++] = a[begin2++];

    //拷贝回去
    for(int i = left;i<=right;i++)
      a[i] = tmp[i];
}
//归并排序
void MergeSort(vector<int>& a,int left,int right)
{
   vector<int> tmp(a.size(),0); 
   _MergeSort(a,left,right,tmp);
}

//计数排序
//版本1:绝对映射,直接开辟最大值+1个空间,把值放到对应的下标位置
//缺点：空间消耗大,针对负数不好处理
void CountSort_version1(vector<int>& a)
{
  int max = a[0];
  for(auto& x: a)
    if(x>max) max =x ;
    
  int* count = new int[max+1]; //开辟最大值+1个空间
  memset(count,0,sizeof(int)*(max+1));//初始化为0
  //建立《绝对》映射,统计次数
  for(int i = 0;i<a.size();i++)
  {
    count[a[i]]++;
  }
  //遍历排序
  int index = 0;
  for(int i = 0 ;i<=max;i++) 
  {
    while(count[i] > 0) //count[i] = x , x表示i这个值在a数组出现的次数
    {
      a[index++] = i;
      count[i]--;
    }
  }
}

//相对映射
//开max - min + 1个空间： [min,max]元素个数就是max - min + 1
//映射在count数组的位置index = a[i]-min 到时放回去原数组的值是:index+min
//针对负数也可以处理
//例子:假设min=-5,则其映射在index = -5+min=-5-(-5)=0位置,最后放回去的值:index+min = 0-5=-5
void CountSort_version2(vector<int>& a)
{
  int max = a[0],min=a[0];
  for(auto& x:a)
  {
    if(x>max) max = x;
    if(x<min) min = x;
  } 
  int* count = new int[max-min+1];//数据范围:[min,max]
  memset(count,0,sizeof(int)*(max-min+1));
  //建立相对映射
  for(int i = 0 ;i<a.size();i++)
    count[a[i]-min] ++;
  //放回去
  int i = 0;
  for(int index =0;index< max-min+1 ;index++)
  {
     while(count[index] > 0)//count[index] = x , x表示index+min这个值在a数组出现的次数
     {
        a[i++] = index+min;
        count[index]--;
     }
  }
}

void QucikSort_NonR(vector<int>& v,int left,int right)
{
  if(left>=right)
    return ;
  stack<int> st;
  st.push(right);
  st.push(left);
  while(!st.empty())
  {
    int begin = st.top();
    st.pop();
    int end = st.top();
    st.pop();
    int keyi = PartSion1(v,begin,end);
    //[begin,keyi-1] [keyi+1,end]
    if(keyi-1 > begin)
    {
      st.push(keyi-1);
      st.push(begin);
    }
    if(end > keyi+1)
    {
      st.push(end);
      st.push(keyi+1);
    }
  }
}
